// packrat.cpp
//
// Copyright (C) 2008  Maksim Sipos <msipos@mailc.net>
//
// This file is a part of the Ripe language project.
//
// Ripe is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#include "util/standard.hpp"
#include "util/packrat.hpp"
#include "util/mem.hpp"

namespace Ripe {

bool MemoKey::operator==(const MemoKey& other)
{
  return nonterm == other.nonterm and location == other.location;
}

Semantic Parsing::apply(Nonterminal nterm, int precedence)
{
  // Find the given nonterminal in the grammar.
  Matcher matcher = NULL;
  grammar.get(nterm, &matcher);
  assert(matcher != NULL);
  return matcher(this, precedence);
}

bool Parsing::consume(uint32_t type, Token** out_token)
{
  if (idx >= tokens->size) return false;

  Token* token = (*tokens)[idx];
  if (token->type == type){
    idx++;
    *out_token = token;
    return true;
  }
  return false;
}

Semantic Parsing::match(Nonterminal nterm, int precedence)
{
  // This function essentially applies the procedure that allows packrat
  // parsers to parse directly left-recursive rules. This algorithm was given
  // in "Packrat Parsers Can Support Left Recursion", A. Warth, J. R. Douglass,
  // T. Millstein. PEPM '08.

  // Record the position on the start.
  uint32_t start_idx = idx;

  // Look-up in the memo table.
  MemoKey key = {nterm, idx};
  MemoValue value;
  if (memo.get(key, &value)) {
    switch(value.status){
      case StatusApplying:
        value.status = StatusDetectedLR;
        memo.set(key, value);
      case StatusDetectedLR:
        return NULL;
      case StatusApplied:
        idx = value.new_idx;
        return value.ast;
    }
  }

  // Now memoize that we are applying this rule.
  value.status = StatusApplying;
  memo.set(key, value);

  // Apply the rule
  Semantic result = apply(nterm, precedence);
  value.ast = result;

  // If match failed, backtracking and memoizing.
  if (result == NULL){
    value.status = StatusApplied;
    value.new_idx = start_idx;
    memo.set(key, value);
    idx = start_idx;
    return NULL;
  }

  // Look-up in the memoization table again.
  memo.get(key, &value);
  switch (value.status){
    case StatusApplied:
    case StatusApplying:
      // No LR detected.
      value.status = StatusApplied;
      value.new_idx = idx;
      memo.set(key, value);
      return result;
    case StatusDetectedLR:
      // Left recursion detected, now we "grow the seed". Begin by pretending
      // that a match succeeded at this place.
      value.status = StatusApplied;

      // matched2 is the index reached in the latest attempt. matched1 is the
      // index reached in previous attempt.
      uint32_t matched2 = idx;
      uint32_t matched1;
      do {
        matched1 = matched2;
        value.ast = result;
        value.new_idx = matched2;
        memo.set(key, value);

        // Backtrack to original call: */
        idx = start_idx;
        result = apply(nterm, precedence);
        if (result == NULL)
          break;
        matched2 = idx;
      } while (matched2 > matched1);
      idx = matched1;
      return value.ast;
  }
  assert_never();
}

Semantic Parsing::parse(Nonterminal start)
{
  idx = 0;
  // This should be the smaller than any other precedence.
  Semantic result = match(start, 0);
  if (idx < tokens->size) {
    // Match failed if it didn't consume all input.
    return NULL;
  }
  return result;
}

bool Parsing::read(Token** out_token)
{
  if (idx >= tokens->size) return false;

  *out_token = (*tokens)[idx];
  idx++;
  return true;
}

State Parsing::save()
{
  return idx;
}

void Parsing::restore(State state)
{
  idx = state;
}

}
